1. Field of the Invention
The present invention relates to circuit design and, more particularly, to component placement in a circuit design.
2. Description of the Prior Art
Integrated circuit and electronic board/package design is subject to complex geometric and electrical rules governing the allowed placement of components. Component placements which fail to abide by these rules may occupy too much area to be economically manufactured, achieve levels of desired performance far below those specified at the outset of the design process, or even fail to perform their desired function correctly.
A “component” may be an individual electronic device (for example, a transistor) or a set of pre-placed devices to be treated as a single, atomic placeable object. A “group” may be a hierarchy of placed components, such as several devices of a sub-circuit, or several sub-circuits placed in a circuit to also be treated as single, atomic object.
A component is conventionally specified by a rectilinear, typically rectangular, outline which completely encompasses its internal geometry and any extra space that must be included around the exterior of the component to ensure compliance with manufacturing rules that specify allowable distances between components. The result of geometrically arranging a plurality of such components on the surface of an IC chip or a board is called a “placement”, or a “layout”, or a “floorplan”.
It is conventional to optimize component placements to minimize some combination of the overall area of a layout, the length of conducting wires (also called “nets”) that connect the components, and the delay to propagate an electrical signal along selected paths of the longest wires in the design. For placement of digital components, strategies of this type often suffice. However, for placements intended to create layouts that incorporate non-digital components, for example, analog components, mixtures of analog and digital components (called “mixed-signal” designs), radio-frequency components (“RF”) and microwave-frequency components, among others, additional geometric constraints are often imposed. These additional geometric constraints maximize the precision with which various electrical quantities (current, voltage, charge, capacitance, inductance, etc.) may be created or manipulated by these placed components, thus enhancing the likelihood of correct electrical function of the final manufactured design.
These geometric constraints come in several well-known styles. The geometric placement constraint styles of relevance to the present invention include symmetries, groups and isolation structures.
Symmetries:
Numerous prior art techniques exist for generating a layout of components when no symmetry, grouping, and/or isolation constraints are present. These conventionally comprise a method to represent the location of each placed component and a method to iteratively perturb or amend this representation to incrementally improve it to a best-quality placement, as measured by a cost function that quantifies the goodness of the placement.
The present invention is a new method for placement that supports standard prior art placement goals for digital components, e.g., wirelength, area, etc., and also supports symmetry, grouping and isolation requirements often associated with analog components.
With reference to FIG. 1, a placement problem typically comprises a set of arrangeable components that may each (for simplicity of description) be treated as rectangular objects. These rectangular objects must be arranged on a layout surface which itself can be treated as a rectangle.
Individual components carry geometric rules that determine the minimum allowed proximity (distance) to each other individual component. In particular, it is normal that placed components may not overlap. The process of “placement” assigns to each rectangular component an absolute (x, y) location, indexed relative to x (horizontal) and y (vertical) coordinate axes suitably defined for the layout surface itself.
With reference to FIG. 2, symmetry constraints impose mirror-like placement constraints on pairs of components. The two elements in the pair are referred to as siblings. A distinguished line segment—called a symmetry line—defines an axis of symmetry for the constraint.
In the simplest form of symmetry, a pair-symmetric constraint mandates that a pair of identical components must be placed as “mirror reflections” of each other about the symmetry line. For a vertical symmetry line, this means identical y (vertical) coordinates, but x coordinates that locate each component an identical distance D away from the symmetry line.
With reference to FIG. 3, and with continuing reference to FIG. 2, the symmetry line can be horizontal or vertical. To this end, the roles of the x and y coordinate values can be interchanged. A distinguished line segment again defines an axis of symmetry for the constraint, only now, this symmetry line is horizontal with respect to the layout surface. For a horizontal symmetry line, this means identical x (horizontal) coordinates, but y coordinates that locate each component an identical distance D away from the central symmetry line.
With reference to FIG. 4, in addition, the pair of components may be required to be in a specific relative orientation with respect to the symmetry line. This can apply for either the vertical or horizontal cases. Any geometric object being placed on a two-dimensional layout surface can be rotated or reflected into one of the eight unique orientations shown in FIG. 5. Pair-symmetric constraints can also optionally mandate the orientation of each component of the pair.
In addition, the pair of components may be required to be in a specific relative orientation with respect to the symmetry line. This can apply for either the vertical or horizontal cases. As shown in FIG. 6, simple pair-symmetric orientation requires the components to be arranged in identical orientations on each side of the line. (Identical left-right orientation for vertical symmetry lines or identical top-bottom orientation for horizontal symmetry lines). However, as shown in FIG. 7, mirror pair-symmetric orientation requires the components to be arranged as mirror images with respect to the symmetry line. (Left-right reversal across a vertical symmetry line or top-bottom reversal across a horizontal symmetry line).
Another type of symmetry constraint, shown in FIGS. 8 and 9, is a self-symmetry constraint. This requires a single component to have its center coordinate located on the symmetry line. Thus, the self-symmetric component extends a distance D on each side of the symmetry line. As shown in FIGS. 8 and 9, self-symmetry can be applied to either a vertical symmetry line or a horizontal symmetry line. As with the case of the pair-symmetric constraint, an optional orientation constraint may be imposed on the single self-symmetric component.
With reference to FIGS. 10 and 11, another type of symmetry constraint is an asymmetry constraint. This requires a single component to have an internal coordinate other than its center point located on the symmetry line. Thus, the asymmetric component extends a distance D1 on one side of the symmetry line and a distance D2 on the other side of the symmetry line, where D1+D2 equals the dimension of the component perpendicular to the symmetry line.
As shown in FIGS. 10 and 11, asymmetry can be applied to either a vertical or a horizontal symmetry line. As with the case of the pair-symmetric constraint, an optional orientation constraint may be imposed on the single asymmetric component.
With reference to FIGS. 12 and 13, another type of symmetry constraint is a fixed symmetric offset constraint. This requires a single component to not overlap the symmetry line but, instead, be separated from the symmetry line by a precise (“fixed”) distance D. Thus, the fixed symmetric offset component is exactly a distance D away on one side of the symmetry line. Another required element of the fixed symmetric offset constraint is which side of the symmetry line the component is required to reside in. As shown in FIGS. 12 and 13, fixed symmetric offset constraints can appear with either vertical or horizontal symmetry lines. As with the case of other symmetry constraints, an optional orientation constraint may be imposed on the component.
With reference to FIG. 14, components that do not participate in any symmetry constraints are referred to as non-symmetric. Symmetric and non-symmetric components can co-exist in the same placement on the same layout surface. As shown in FIG. 15, multiple different symmetry lines can also co-exist on a single layout surface. Individual components will be identified as either non-symmetric or bound to a particular symmetry line. When the symmetry line extends across the entire layout surface, it is referred to as a global symmetry line. When the symmetry line extends only across a portion of the layout surface, it is referred to as a local symmetry line. Multiple local and global, horizontal and vertical symmetry lines can arbitrarily co-exist on the same layout surface, each with an arbitrary collection of components with arbitrary symmetry constraints imposed on them.
Groups:
With reference to FIGS. 16 and 17, group constraints require sets of individual components to be placed near each other. In addition, group constraints define, for the set of components in a group, a minimum bounding rectangle. This rectangle defines the components of the group, and imposes the additional constraint that no component that is not part of the group can be placed inside this rectangle.
With reference to FIG. 18, the minimum bounding rectangle of a group can be treated like a single placeable component. Thus, groups can also have symmetry constraints. A pair of identical groups can form a symmetric pair. A single group can be self-symmetric, asymmetric, non-symmetric, or can have a fixed symmetric offset. Groups can be bound to local or global symmetry lines, and horizontal or vertical symmetry lines.
With reference to FIG. 19, the minimum bounding rectangle of a group can also or alternatively be treated like it was the layout surface itself. Thus groups can also have internal, local symmetry lines. Components inside of a group can be bound to this local symmetry line or they can be non-symmetric. The local symmetry line can be group-global, namely, it traverses the entire dimension of the group, or it can be group-local, namely, it traverses partially but not entirely across one dimension of the group. A single group can have any number of such internal symmetry lines. A group with internal symmetries can itself be treated as a single minimum bounding rectangle that obeys any symmetry constraint. These are referred to as hierarchical symmetry constraints.
Isolation Structures:
With reference to FIGS. 20 and 21, isolation constraints handle situations where individual or hierarchical placed components or groups may be electrically sensitive to disruption from other components or groups placed nearby. One mechanism for mitigating this problem is to add a special, isolation structure around portions of the perimeter of each sensitive component. These isolation structures appear as geometric bands around portions or all of the perimeter of a component, increasing its size, and changing its spacing rules with respect to other placed components or groups.
With reference to FIGS. 22 and 23, groups can also have isolation constraints. For groups, these isolation structures appear as geometric bands around portions or all of the perimeter of the group's minimum bounding rectangle, changing its geometric size and spacing rules with respect to other placed components or groups.
All of these three styles of constraints, namely, symmetries, groups and isolation structures, can co-exist in one placement. Individual components may participate in symmetry constraints, be parts of groups, or have individual isolation structures. Likewise, groups themselves can have internal symmetries, participate in group/hierarchical symmetries external to themselves, and have group-level isolation structures. Groups can be nested inside each other to define arbitrary layout hierarchies.
Many prior art methods exist for generating a layout of components when symmetry, grouping, and isolation constraints are not needed. These conventionally comprise a method to represent the location of each placed component, and a method to iteratively perturb this representation to incrementally improve it to a best-quality placement, as measured by an auxiliary cost function.
These prior art methods, however, do not work when the presence of arbitrary combinations of symmetry, grouping, or isolation constraints exist. While prior art methods exist that partially address some of these constraints, all of the prior art methods for handling symmetries suffer from at least one of the following problems:                They cannot guarantee the ultimate geometric legality of the placement, e.g., components may overlap;        They cannot guarantee that all symmetry constraints are satisfied in the final placement;        The process of evaluating the feasibility of satisfying all symmetries for each placement solution candidate is inefficient, e.g., quadratic in the number of components;        They cannot support the full range of required constraints required, namely, self and pair symmetry, asymmetry and non-symmetry, fixed symmetric offsets, groups, group and hierarchical symmetries, isolation structures for components and groups.        
The present invention overcomes the above problems and others by providing a method that utilizes a novel data structure called a tree structure that supports all of the foregoing constraints. Every placement solution candidate generated during iterative improvement will satisfy all the constraints. The method of generating these solution candidates, and the method of evaluating the cost function which determines the quality of each solution candidate, are both novel and efficient. The method requires only a single binary tree data structure with suitable annotations. Evaluating the quality of any placement solution requires only searches of this tree structure. In particular, the method does not require the construction of any secondary or auxiliary data structures to check that the constraints can be met, or to evaluate the cost of a placement.